package cn.dapeng.tree.binary;

/**
 * 判断一个树是否是平衡二叉树
 * <p>
 * <p>
 * 平衡二叉树定义：左树与右树的高度差小于2
 * <p>
 * 搜索二叉树定义： 对于任何子树，左树的任何节点都小于跟节点，右树的任何节点都大于跟节点
 * <p>
 * 设x为一个二叉树的头节点
 * 1.x的左树是平的
 * 2.x的右树是平的
 * 3. x左树高-x右数高，绝对值小于2
 */
public class CheckBalanceTree {

    public static boolean isBalance(TreeNode x) {
        return process(x).isBalance;
    }

    public static Info process(TreeNode x) {
        if (x == null) {
            return new Info(true, 0);
        }
        // 搜集左树、右树的信息
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        // 当前节点的高度等于左树和右树中较大的高度 + 1
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        // 如果左树是平的，右树也是平的，并且左右树高度差小于2，那么当前树是平衡二叉树
        boolean isBalance = leftInfo.isBalance && rightInfo.isBalance && Math.abs(leftInfo.height - rightInfo.height) < 2;

        return new Info(isBalance, height);
    }

    public static class Info {
        public boolean isBalance;

        public int height;

        public Info(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

}
